// 给定一个整数k和整数n，分别代表k枚鸡蛋和可以使用的一栋从第1层到第n层楼的建筑
// 已知存在楼层f，满足0 <= f <= n，任何从高于f的楼层落下的鸡蛋都会碎，从f楼层或比它低的楼层落下的鸡蛋都不会碎
// 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层x扔下，如果鸡蛋碎了，就不能再次使用它，如果鸡蛋没碎，则可以再次使用
// 要求：计算并返回要确定f确切值的最小操作次数是多少

// 解题思路3，动态规划 + 逆向思维
// 至少需要扔几次鸡蛋才能保证无论f是多少层，都能将f找出来
// 逆向思维下，题目可以变为，已知有k个鸡蛋，最多扔x次鸡蛋，求最多可以检测多少层
// 我们把未知条件 【扔鸡蛋的次数】 变为了已知条件，将 【检测的楼层个数】变为了未知条件
// 这样如果求出来的【检测的楼层个数】大于等于n，则说明1-n层数都考虑全了，f值也就明确了，我们只需要从符合条件的情况里，找出【扔鸡蛋的次数】最少的次数即可

// 1. 划分阶段，按照鸡蛋个数，扔鸡蛋的次数进行阶段划分
// 2. 定义状态，定义状态dp[i][j]表示为，一共有i个鸡蛋，最多扔j次鸡蛋（碎不碎都算一次）的条件下，最多可以检测的楼层个数
// 3. 状态转移方程
//      我们现在有i个鸡蛋，j次扔鸡蛋的机会，现在尝试在1-n层中的任意一层x扔鸡蛋
//          1. 如果鸡蛋没碎，剩下i个鸡蛋，还有j- 1次扔鸡蛋的机会，最多可以检测dp[i][j-1]层楼层
//          2. 如果鸡蛋碎了，剩下i-1个鸡蛋，还有j-1次 扔鸡蛋的机会，最多可以检测dp[i-1][j-1]层楼层
//          3. 再加上我们扔鸡蛋的第x层，i个鸡蛋，j次扔鸡蛋的机会，最多可以检测 dp[i][j-1] + dp[i-1][j-1] + 1
//      状态转移方程为： dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + 1
// 4. 初始条件，当鸡蛋数位1，只有1次扔鸡蛋的机会时，最多可以检测1层，dp[1][1] = 1
// 5. 最终结果
// 根据我们之前定义的状态，dp[i][j] 表示为：一共有 i 个鸡蛋，最多扔 j 次鸡蛋（碎没碎都算 1 次）的条件下，最多可以检测的楼层个数。
// 则我们需要从满足 i == k 并且 dp[i][j] >= n（即 k 个鸡蛋，j 次扔鸡蛋，一共检测出 n 层楼）的情况中，找出最小的 j，将其返回。
function superEggDrop(k, n) {
    let dp = new Array(k + 1).fill(0).map(_ => new Array(n + 1).fill(0))
    dp[1][1] = 1
    for (let i = 1; i <= k; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1
            if ( i === k && dp[i][j] >= n) {
                return j
            }        
        }        
    }
    return n
}

let k = 2, n = 6
console.log(superEggDrop(k, n))
